1. Field
This invention relates to the field of queuing in computer systems. In particular, the invention relates to transaction capable queuing.
2. Description of the Related Art
A queue of messages is a widely used concept in computing. In particular, in messaging middleware a queue can be used to buffer messages sent between applications. Often the performance of these queues is critical to the performance of the system as a whole; therefore much research has gone into creating efficient implementations.
If the system calls for a strictly FIFO (First-In-First-Out) queue, there are a large number of ways of writing a lock-free/wait-free queue that will scale to a large number of applications simultaneously putting and getting messages from such a queue. The drawback of such designs is that they tend to be complex and slower than a simpler queue in the case where there is a single application putting and a single application getting messages from the queue. Such algorithms usually rely on the ability to perform atomic operations like compare-and-swap (CAS) (discussed later). These atomic operations are usually a single machine instruction and are not considered a lock in the conventional sense.
Often a strictly FIFO queue is not sufficient, for example JMS (Java® Message Service) requires that queues support transactions so that messages can be put/got from the queue in two stages. First the message(s) are put/got, then (potentially as a group) the messages are committed or instead all the puts/gets are cancelled, which is known as a rollback. In order to preserve message order (and to simplify the commit operation which should be fast and should NOT fail), implementations of transactions often involve leaving messages involved in a transaction on the queue but in a “locked” state so that they cannot be accessed by other applications. Queues that implement transactions in this fashion are no longer FIFO; the messages at the head/tail of the queue may be locked and the first message available to retrieve may actually be in the middle of the list of messages. Java and all Java-based trademarks and logos are trademarks or registered trademarks of Oracle and/or its affiliates.
As far as is known, no lock-free algorithm exists that works for this type of non-FIFO queue.
A “two-lock” FIFO queue is known which allows an application to be putting to the queue and simultaneously a different application can be getting so that messages can efficiently stream though the queue. If it is possible that multiple applications might need to put (or get) simultaneously, then the right to put (or get) is serialized by a lock (thus the two locks are a put-lock and a get-lock). An explanation of how a two-lock queue may be implemented is provided by Herb Sutter at http://www.ddj.com/cpp/211601363.
In the two-lock FIFO queue, no serialization occurs between the putter and getter—the getter always gets the first message on the queue regardless of what the putter is doing. In the non-FIFO transaction supporting queue mentioned, there can be no such isolation. Getting applications need to efficiently find a message to get and if a putting application commits a message “before” the position in the queue at which the getting application is examining, the getter must find that message instead.
Transactions are supposed to be atomic, which means that if two messages put to the queue are committed in a single transaction, the message that was put first must be got first. This underlines the need for efficient communication between putter and getter. If the getter was just examining messages one by one on the queue, when it finds the first message in the transaction it may still be locked but by the time the second message is examined (if the commit has occurred) then that message may be available and the wrong message may be got from the queue.
Therefore, there is a need in the art to address the aforementioned problems.